package com.haidechizi.leetcode;

import java.util.Stack;

/**
 * @author: wangdejun
 * @create: 2020-04-18 17:26
 **/
public class _1293_网格中的最短路径 {

    int result = -1;

    public int shortestPath(int[][] grid, int k) {
        Stack<int[]> stack = new Stack<>();
        walk(stack, grid, 0, 0, k, 0);
        return result;
    }

    public void walk(Stack<int[]> stack, int[][] grid, int i, int j, int k, int sum) {
        if (i >= grid.length || i < 0) {
            return;
        }
        if (j >= grid[0].length || j < 0) {
            return;
        }
        if (contains(stack,new int[]{i, j})) {
            return;
        }
        stack.add(new int[]{i, j});
        sum += grid[i][j];
        if (sum > k) {
            stack.pop();
            sum -= grid[i][j];
            return;
        }
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            if (result == -1) {
                result = stack.size() - 1;
            } else {
                result = Math.min(result, stack.size() - 1);
            }
        }
        // 右
        walk(stack, grid, i, j + 1, k, sum);

        // 下
        walk(stack, grid, i + 1, j, k, sum);

        // 左
        walk(stack, grid, i, j - 1, k, sum);
        // 上
        walk(stack, grid, i - 1, j, k, sum);
    }

    public boolean contains(Stack<int[]> stack, int[] arr) {
        for (int[] temp : stack) {
            if (temp[0] == arr[0] && temp[1] == arr[1]) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 1, 1}, {1, 1, 1}, {0, 0, 0}};
        new _1293_网格中的最短路径().shortestPath(grid, 1);
    }
}
